package com.fengye.algorithms.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author fengye
 * @Date 2023/4/24 11:21
 **/
public class FindAllAnagramsInAString438 {

    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();

        if(s == null || p == null) {
            return res;
        }

        int pLen = p.length();
        int sLen = s.length();

        if(sLen < pLen) {
            return res;
        }

        int[] pCounts = new int[26];
        int[] sCounts = new int[26];

        for(int i=0;i<pLen; i++) {
            pCounts[p.charAt(i) - 'a']++;
            sCounts[s.charAt(i) - 'a']++;
        }

        if(Arrays.equals(pCounts, sCounts)) {
            res.add(0);
        }

        for(int i=0;i<sLen-pLen;i++) {
            sCounts[s.charAt(i) - 'a']--;
            sCounts[s.charAt(i+pLen) - 'a']++;
            if(Arrays.equals(pCounts, sCounts)) {
                res.add(i+1);
            }
        }

        return res;
    }

    public List<Integer> findAnagrams1(String s, String p) {
        List<Integer> res = new ArrayList<>();

        if(s == null || p == null) {
            return res;
        }
        char[] pc = p.toCharArray();
        int pLen = p.length();
        Arrays.sort(pc);
        String np = new String(pc);

        for (int i = 0; i < s.length() - pLen; i++) {
            char[] sub = s.substring(i, i+pLen).toCharArray();
            Arrays.sort(sub);
            if(new String(sub).equals(np)) {
                res.add(i);
            }
        }

        return res;
    }
}
